1. Field of the Invention
The present invention relates to a coding method which is suited to obtain and output, at a high speed, a code number determined in accordance with an array order of a plurality of texts arrayed in a tree structure, a semiconductor memory for implementing the coding method, a decoder suited to the semiconductor memory and a method for identifying hand-written characters at a high speed by using the semiconductor memory.
2. Description of the Related Art
A method by which a plurality of retrieval data (texts) are ideally arrayed while permitting reappearance of the data and data (code numbers) to be retrieved which is predetermined in accordance with the order of array of the texts has conventionally been taken into consideration.
The following describes an art related to the present invention described later with an example of identification of hand-written characters.
Conventionally, it has often been attempted to identify hand-written characters. As an approach for identifying hand-written characters, a method has been proposed which utilizes the features particularly remarkable in Kanji characters as described below:
(1) A shape of a stroke is approximately predetermined. PA1 (2) A pause between strokes can be clearly checked if, for example, a restrictive requirement "write in Kaisho (square style)" is prescribed. PA1 a code number is assigned to each node of the tree structure, and PA1 a node toward which a retrieval should advance is determined in accordance with an entered text and a node number of a node where the current position of retrieval is identified when the text is entered. PA1 a first input part for entering a first bit pattern from an external source, PA1 a second input part which has a register for storing a second bit pattern which partly forms the contents read out from the semiconductor memory and entering the second bit pattern stored in the register, PA1 a correspondence detection part for selecting a memory area in which the contents to be read out from a number of memory areas in which a number of specified contents are stored by decoding the bit patterns entered both from the first input part and from the second input part, and PA1 a hit detection part for detecting a memory area selected by the correspondence detection part from a number of specified memory areas, and characterized in that the register preserves the contents stored when any of a number of specified memory areas is not selected by the correspondence detection part. PA1 a number of memory areas which are divided into a plurality of blocks and each of which comprises as many memory cells as the predetermined number of bits, PA1 a retrieval data input terminal through which retrieval data is entered, PA1 a correspondence detection part for storing a number of comparison data respectively corresponding to a number of memory areas, comparing the retrieval data entered through the retrieval data input terminal and a number of comparison data, and outputting a correspondence signal for selecting the memory area corresponding to the comparison data which matches with the retrieval data of a number of comparison data, PA1 a plurality sense amplifiers which are provided as many as the number of memory cells for the predetermined number of bits and amplify to read out the contents stored in the memory cells, and PA1 a block selection circuit which selects a block including the memory area selected with the decode signal from a plurality of blocks according to the correspondence signal outputted from the correspondence detection part and connecting the memory cells in the selected block to the sense amplifier. PA1 a memory section provided with a number of memory areas each of which consists of a first and second output data storage areas where specified first and second output data which form specified output data is stored, PA1 a first input part for entering first retrieval data from an external source, PA1 a second input part provided with a register for storing second retrieval data and an input selector for selectively entering the retrieval data entered from the external source and the first output data read out from the memory section into the register as the second retrieval data, PA1 a correspondence detection part provided with a plurality of comparison data storage areas each of which consists of first and second comparison data storage areas which respectively store specified first and second comparison data and compare the first and second comparison data with the first and second retrieval data entered from the first and second input parts and which respectively correspond to a number of memory areas and a number of correspondence detection circuits and a plurality of correspondence detection circuits which are arranged respectively corresponding to the comparison data storage areas and the memory areas and output decode signals which command reading out of the output data stored in the corresponding memory areas when the fist and second comparison data stored in the first and second comparison data storage areas which form the corresponding comparison data storage areas respectively correspond to the first and second retrieval data, PA1 a first masking circuit for treating a number of the first comparison data storage areas while assuming that the first comparison data corresponds to the first retrieval data regardless of the state of the first comparison data stored in the first comparison data storage area, and PA1 a second masking circuit for treating a number of the second comparison data storage areas while assuming that the second comparison data corresponds to the second retrieval data regardless of the state of the second comparison data stored in the second comparison data storage area. PA1 an inference mechanism for classifying the strokes of a hand-written character into one or a plurality of basic strokes and PA1 a semiconductor memory in which a plurality of the basic strokes are arranged at the nodes of a tree structure while permitting reappearance of these basic strokes, character codes are arranged at these nodes as required and the character codes corresponding to the basic stroke chain for converting the basic stroke chain which consists of the basic strokes arranged in sequence along a branch following route by obtaining a character code assigned to a node which is positioned at an end of a branch train of the tree structure, and which has a decoder section provided with a first input part for entering a first bit pattern which denotes the basic stroke, a second input part which has a register for storing a second bit pattern which denotes the node number assigned to each of respective nodes and enters the second bit pattern stored in this register and a correspondence detection part which detects a node which corresponds to the node determined by these first and second bit pattern inputs in accordance with the first and second bit pattern inputs, and a memory section which has a number of memory areas which store a first bit pattern denoting a node number assigned to each of respective nodes and a third bit pattern denoting the character code when a character code is assigned to each node and is provided with a number of memory areas corresponding to the nodes and is provided with a node number output part which outputs the first bit pattern corresponding to the node number assigned to the node detected by the correspondence detection part and enters it into the register and a character code output part which outputs the third bit pattern denoting the character code when the character code is assigned to the node detected by the correspondence detection part and characterized in that a stroke chain of a hand-written character is converted to one or a plurality of basic strokes by using the reasoning mechanism and a basic stroke chain is converted to a character code by using the semiconductor memory.
Specifically, a number of sets of basic strokes of Kanji characters or the like, which are respectively patterned by modelling the strokes of Kanji characters or the like, are prepared and a stroke of a hand-written character which is entered is compared by pattern-matching with a basic stroke and represented by the most similar basic stroke, thereby a basic stroke chain consisting of the basic strokes which are arrayed in an order of writing, including information which indicates an entry order of the strokes of each hand-written character, is obtained. Then this basic stroke chain is converted to a character code, that is, the hand-written character is thus identified.
Methods which can be adopted to obtain the basic strokes from the strokes of a hand-written character include, for example, forward reasoning, backward reasoning, blackboard system, neural network system, fuzzy reasoning, etc.
For example, in "`On-line Hand-written Characters Identifying Method by Applying Fuzzy Reasoning` Hirobumi Tamori et al, a treatise magazine of the Society of Electronic Information Communications D-II Vol.J74-DII No.2 pp.166-174, February 1991" (hereinafter simply referred to as the "literature"), a method for identifying hand-written characters by using a fuzzy reasoning is introduced as shown by the title of the treatise.
In identification of hand-written characters by using the above described various methods, a point to be noted is how the basic stroke chains should be converted to the character codes. The following describes an example of conventional method for converting the basic stroke chains to the character codes, referring to a practical example.
TABLE 1 ______________________________________ Basic Stroke Basic Stoke Code (2 bits) ______________________________________ T0 00 T1 01 T2 10 T3 11 ______________________________________
TABLE 2 ______________________________________ Basic Stoke Character Chain Code (Code) Character Code (10 bits) ______________________________________ T0 C1 0 0 0 0 0 0 0 0 0 1 T0.fwdarw.T0 C3 0 0 0 0 0 0 0 0 1 0 T0.fwdarw.T1 C4 0 0 0 0 0 0 0 1 0 0 T0.fwdarw.T3 C5 0 0 0 0 0 0 1 0 0 0 T1.fwdarw.T2 C7 0 0 0 0 0 1 0 0 0 0 T0.fwdarw.T0.fwdarw.T1 C8 0 0 0 0 1 0 0 0 0 0 T0.fwdarw.T0.fwdarw.T2 C9 0 0 0 1 0 0 0 0 0 0 T1.fwdarw.T0.fwdarw.T0 C10 0 0 1 0 0 0 0 0 0 0 T1.fwdarw.T2.fwdarw.T1 C11 0 1 0 0 0 0 0 0 0 0 T1.fwdarw.T2.fwdarw.T3 C12 1 0 0 0 0 0 0 0 0 0 ______________________________________
Table 1 is a comparison table of the basic strokes T0, T1, T2 and T3 and the basic stroke codes each of which consists of two bits and is identified to be identical with one of the basic strokes T0, T1, T2 and T3, and Table 2 is a comparison table of the basic stroke chains each of which consists of an array of basic strokes and the character codes assigned to these basic stroke chains.
FIG. 24 shows an example of the basic strokes which are arrayed in a tree structure.
In FIG. 24, two branches are extended from the top node (peak) and basic strokes T0 and T1 are respectively arranged at the nodes of the ends of these branches. Character code C1 is assigned to the node where the basic stroke T0 is arranged whereas no character node is assigned to the node where the basic stroke T1 is arranged. Further three branches are extended from the node where the basic stroke T0 is arranged and basic strokes T0, T1 and T3 are arranged at the nodes of the ends of these three branches. Character codes C3, C4 and C5 are assigned to these nodes. Of these nodes, further two branches are extended from the node where the basic stroke T0 is arranged and basic strokes T1 and T2 are arranged at the nodes of the ends of these two branches and character codes C8 and C9 are assigned to these nodes. Two branches are extended from the node in the top stage where the basic stroke T1 is arranged and basic strokes T0 and T2 are respectively arranged at the nodes of the ends of these two branches and the character code C7 is assigned to the node where the basic stroke T2 is arranged of the above two nodes. In addition, one and two branches are extended from the nodes where basic strokes T0 and T2 are arranged and the basic stroke T0 is arranged at the node of the end of the branch extended from the node where the basic stroke T0 is arranged and the character code 10 is assigned to this node while basic strokes T1 and T3 are arranged at the nodes of the ends of two branches extended from the node where the basic stroke T2 is arranged and character codes C11 and C12 are assigned to these nodes. In FIG. 24, node numbers (0) and (1) are assigned to the top node and the node where the basic stroke T0 is arranged and the character code C1 is assigned. These node numbers (0) and (1) are assigned for convenience in the description related to the present invention described later and, in this description, the concept of "node number" is not required.
The following describes a case for obtaining a character code C4 corresponding to basic stroke chain T0.fwdarw.T1 along which basic strokes T0 and T1 are arranged in this order.
When the first basic stroke T0 (basic stroke code `00`) is entered, the addresses where basic strokes T0 and T1 which are arranged at the first two nodes (the highest stage in FIG. 24) of the tree-structured data are entered into the storage, basic stroke codes `00` and `01` are outputted in sequence and the outputted basic stroke codes `00` and `01` are compared in sequence with the entered basic stroke code `00`. In this case, it is assumed that the basic stroke T0 (basic stroke code `00`) is stored in the first address of the storage and an address on the storage where the basic stroke T0 which corresponds to the entered basic stroke T0 is specified by one access operation to the address and one comparison operation. This means that the retrieval advances to the node where the basic stroke T0 is arranged while following the left side branch of two branches in the top stage in FIG. 24.
When the basic stroke T1 (basic stroke data `01`) is entered, the contents of the address specified as above on the storage is referred, the addresses of basic strokes T0, T1 and T3 arranged at the nodes of the ends of branches extended from the node with the basic stroke T0 are entered in sequence into the storage to obtain basic strokes T0, T1 and T3 and these basic strokes T0, T1 and T3 thus obtained in sequence are compared with the basic stroke T1 entered. If it is assumed that basic strokes T0, T1 and T3 are stored in sequence, the stored basic stroke T1 is positioned at the second place and therefore an address on the storage where the basic stroke T1, which corresponds to the entered basic stroke T1, is stored is specified by two address accesses and two pattern matching comparisons. This means that the retrieval advances to the node which forms the second stage from the top in FIG. 24 with the basic stroke T1 arranged whereby the character code C4 assigned to this node is obtained and outputted.
Here the basic stroke chain T0.fwdarw.T1 is described. In this case, the character code 4 is obtained by three address accesses and three pattern matching comparisons.
The conventional example shows a simplified example. If the stages of the tree structure shown in FIG. 24 respectively have extremely large numbers of nodes, there is a problem that a desired character code can only be obtained by an extremely large number of times of address accesses and pattern matching comparisons and it takes a long period of time to obtain the desired character code.
In the above description of the method for identification of hand-written characters as an example, words `basic stroke`, `basic stroke chain` and `character code` are used to facilitate understanding. However, the present invention described later is capable of covering a wide range of application in addition to the identification of hand-written characters and therefore, in the following description, generalized words `text`, `text chain, and `code number` are used instead of "basic stroke`, "basic stroke chain` and `character code`.
An object of the present invention described later is to provide a coding method and a semiconductor memory for realizing this coding method which are capable of solving the above described problems and obtaining a desired code number within an extremely short period of time even if a number of nodes are arrayed in each stage of a tree structure for data. The following further describes other related arts before the detailed description of the present invention.
FIG. 25 is an approximate configuration showing an example of a conventional semiconductor memory.
This semiconductor memory is provided with a memory section 1 which comprises a number of memory areas each of which consists of a plurality of memory cells as many as the predetermined number of bits (m bits) (i.e. one word) and a word line 4 is extended from a row decoder 2 to each of memory areas. In this case, the memory section 1 is divided into a plurality of blocks 1-1, 1-2, . . . , 1-n.
Each of blocks 1-1, 1-2, . . . , 1-n comprises a number of memory areas, bit lines 6-1-1, 6-2-1, . . . , 6-n-1 extended to the uppermost memory cells which form the memory areas of blocks 1-1, 1-2, . . . , 1-n are connected to a sense amplifier 10-1 through transistors 8-1-1, 8-2-1, . . . , 8-n-1, bit lines 6-1-2, 6-2-2, . . . , 6-n-2 extended to the second memory cells from the top which form the memory areas are connected to a sense amplifier 10-2 through transistors 8-1-2, 8-2-2, . . . , 8-n-2, subsequent bit lines are similarly connected and bit lines 6-1-m, 6-2-m, . . . , 6-n-m extended to the lowermost memory cells which form the memory areas are connected to a sense amplifier 10-m through transistors 8-1-m, 8-2-m, . . . , 8-n-m. Gates of transistors 8-1-1, 8-1-2, . . . , 8-1-m; 8-2-1, 8-2-2, . . . , 8-2-m; . . . ; and 8-n-1, 8-n-2, . . . , 8-n-m are connected with a column selection circuit 24 through control lines 12-1, 12-2, . . . , 12-n which are respectively provided for blocks 1-1, 1-2, . . . , 1-n.
When address data AD is entered into the semiconductor memory which is constructed as described above, the lower bit part of address data AD entered is entered into the row coder 2 and the higher bit part is entered into the column selection circuit 14. In the row decoder 2, a memory area is selected according to the data of the lower bit part of address data AD, and a logic `1` decode signal which indicates that the memory area is selected is outputted to a word line extending to the memory area while, simultaneously, in the column selection circuit 24, a logic `1` control signal is outputted to a control line 12-2 corresponding to a block which includes the memory area selected in accordance with the data of the higher bit part of address data AD (in this case, as an example, the selected memory area is assumed to belong to block 1-2). The bit information stored in the memory cells which form the selected memory area is amplified in sense amplifiers 10-1, 10-2, . . . , 10-m through bit lines 6-2-1, 6-2-2, . . . , 6-2-m extending to the block 1-2 which are connected with sense amplifiers 10-1, 10-2, . . . , 10-m and the contents stored in the selected memory area are read out to output terminals 16-1, 16-2, . . . , 16-m.
If the semiconductor memory is configured as described above, sense amplifiers 10-1, 10-2, . . . , 10-m need not be provided as many as the number of bit lines (m.times.n lines in the example shown in FIG. 25) and rn sets of sense amplifiers are satisfactory in case of the example shown in FIG. 25. In this case, since the sense amplifiers 10-1, 10-2, . . . , 10-m respectively have a larger chip area than the memory cells for the reason of their configuration, a clearance between the memory cells is limited by the size of the sense amplifier and a number of memory cells cannot be arranged in high density when the sense amplifiers are provided, for example, respectively for bit lines 6-1-1, 6-1-2, . . . , 6-1-m; 6-2-1, 6-2-2, . . . , 6-2-m; . . . ; 6-n-1, 6-n-2, . . . , 6-n-m whereas, in case of a configuration with a reduced number of sense amplifiers, the clearance between bit lines can be reduced without limitation due to the size of the sense amplifiers and therefore a high density semiconductor memory can be realized.
The following continues the description of the related arts.
Conventionally, those decoders, which are constructed to enter the bits of an address denoted by, for example, a 16-bit pattern into 16 input lines, respectively, and output a decode signal to one of approximate 65 K output lines (word lines) which are discriminated by this 16-bit pattern, have widely been used, for example, in the address decoders of memories.
FIG. 26 is a circuit diagram showing an example of the conventional decoder constructed as described above. In this case, however, a circuit with four input lines is shown for simplification.
Further for simplification, the same symbols are assigned to the input lines and the bit signals entered from these input lines.
In this description, the AND gates having as many input terminals as the number of input lines (four lines) are provided as many as the number of output lines, bit signals a.sub.0, a.sub.1, a.sub.2 and a.sub.3 entered from four input lines a.sub.0, a.sub.1, a.sub.2 and a.sub.3 are directly entered into the AND gates, or one or a plurality of these signals are inverted and entered into the AND gates whereby the decode signals are thus outputted from the AND gates. In this case, the inverted signals of the signals a.sub.0, a.sub.1, a.sub.2 and a.sub.3 are denoted as a.sub.0 *, a.sub.1 *, a.sub.2 * and a.sub.3 *.
In the example shown in FIG. 26, a decode signal "1" is outputted from, for example, the top stage AND gate in FIG. 26 when all of input signals a.sub.0, a.sub.1, a.sub.2 and a.sub.3 have a logic level "1" and a decode signal "1" is outputted from the second stage AND gate when input signal a.sub.0 has a logic level "0" and input signals a.sub.1, a.sub.2 and a.sub.3 have a logic level "1".
If a decoder is constructed as shown in FIG. 26 , the AND gate circuits provided with many input terminals are required accordingly as the number of input lines increases. An increased number of terminals will hinder signal transmission to be carried out at higher speeds and, for further speeding up of signal transmission, large-sized transistors will be required contrary to the demands for high density installation.
To solve this problem, a predecoding type decoder has been proposed.
FIG. 27 is a circuit diagram showing an example of a predecoding type decoder.
This pre(decoding type decoder has four input lines a.sub.0, a.sub.1, a.sub.2 and a.sub.3 which are divided into two input lines a.sub.0 and a.sub.1 and other two input lines a.sub.2 and a.sub.3 for which predecoders 17 and 18 are respectively provided and is constructed to finally obtain the same decode signal as in case of the decoder shown in FIG. 26 from the main decoder of the following stage. When the predecoding system is adopted, the decoder can be configured with, for example, AND gates with less input terminals as shown in FIG. 27 and therefore a compact high speed decoder can be realized.